package code;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class JumpGame {
	/*
	 * ���������ģ����ˣ�д���е�����
	 */
	public boolean dfs(int[] A,int n,int p,boolean[] vis){
		if(p==n-1){
			return true;
		}
		if(vis[p])
			return false;
		for(int i=n-1;i>p;i--){
			if(A[p]>=i-p){
				return dfs(A,n,i,vis);
			}
		}
		vis[p]=true;
		return false;
	}
	
	/*
	 * ��һ����������İ汾
	 */
	
    public int jump(int[] A) {
    	int n=A.length;
    	int[] dis=new int[n];
    	if(n==1)	return 0;
    	Queue<Integer> queue=new LinkedList<Integer>();
    	
    	queue.add(0);
    	dis[0]=0;
    	while(!queue.isEmpty()){
    		int head=queue.poll();
    		for(int i=head+1;i<n;i++){
    			if(dis[i]==0 && A[head]>=i-head){
    				dis[i]=dis[head]+1;
    				queue.add(i);
    				if(i==n-1){
    					return dis[i];
    				}
    			}
    			if(A[head]<i-head)	
    				break;
    		}
    	}
    	return 0;
    }
    /*
     * �ѿ޵��ڲ���...
     * �ٷ��İ汾��̰��...
     * ��¼��ǰ��λ��i���ܱ�������������ǰ��A[i]������һ���������µ�����ӣ���ô����
     * ̫������
     */
    
    public boolean canJump(int[] A) {
    	int n=A.length;
    	if(n==1)	return true;
    	int step=A[0];
    	for(int i=1;i<n;i++){
    		step--;
    		if(step<0)	return false;
    		if(step<A[i]){
    			step=A[i];
    		}
    	}
    	return true;
    }
    /*
     * ��0��n-1�����ٲ������Լ����벻�������Ĺ̶�˼ά������һ�н�����
     * ����̰��
     * ��ǰ���ߵ�i��ʱ�����ٵĲ���step
     * curReach��ʾ��ǰ��С��������ܵ��ĵط�
     * curMax��ʾ��ǰ��0...i�����£��ܵ������Զ�ط�
     */
    public int jumpII(int A[]){
    	int step=0;
    	int curMax=0;
    	int curReach=0;
    	int n=A.length;
    	for(int i=0;i<n;i++){
    		if(curReach<i){
    			step++;
    			curReach=curMax;
    		}
    		curMax=curMax<i+A[i]?i+A[i]:curMax;
    	}
    	return step;
    }
    public static void main(String[] args){
//    	int[] A={2,0,6,9,8,4,5,0,8,9,1,2,9,6,8,8,0,6,3,1,2,2,1,2,6,5,3,1,2,2,6,4,2,4,3,0,0,0,3,8,2,4,0,1,2,0,1,4,6,5,8,0,7,9,3,4,6,6,5,8,9,3,4,3,7,0,4,9,0,9,8,4,3,0,7,7,1,9,1,9,4,9,0,1,9,5,7,7,1,5,8,2,8,2,6,8,2,2,7,5,1,7,9,6};
    	int[] A={3,2,1,0};
    	JumpGame jg=new JumpGame();
    	System.out.println(jg.jump(A));
    }
}
